1. Field
This application relates to apparatus and methods for computing the position of a mobile device by use of wireless signals, such as from GPS systems.
2. Related Art
Position location devices are becoming increasingly popular, not only for ships at sea and adventurers in the wilderness, but also for the average person with a cell phone. The increasing popularity of personal position location devices has encouraged development of rapid, high sensitivity methods for acquiring the signals used to determine position.
Position location technologies typically utilize wireless signals concurrently transmitted from known locations to determine position. In GPS systems, these signals are concurrently transmitted from a multiplicity of satellites at a known time, and with a predefined frequency. On the ground, a GPS receiver acquires a signal from each satellite within its view of the sky. The times of arrival of the signals along with the exact location of the in-view satellites and the exact times the signals were transmitted from each satellite are used to locate the position of the GPS receiver via a trilateration calculation.
The acquisition of signals from the GPS satellites can be difficult due to a number of factors. For example, GPS signals are transmitted at a relatively low power, and from a great distance. By the time the GPS signals travel from earth orbit to a receiver, their initially low power has been greatly reduced, rendering the signal extremely weak at the receiver. The received signal levels may be further weakened by building blockage effects, such as may occur during indoor reception or reception in urban canyon environments.
There are two principal functions of GPS receiving systems: (1) computation of the pseudoranges to the various GPS satellites, and (2) computation of the position of the receiving platform using these pseudoranges and satellite timing and ephemeris (position) data. The pseudoranges measure the time delays (or equivalently the ranges) between the satellites and the GPS receiver with a bias due to the local clock. In conventional autonomous GPS receivers, the satellite ephemeris and time of transmission data are extracted from the GPS signal once it is acquired and tracked. Collecting this information normally takes a relatively long time (30 seconds to several minutes) and must be accomplished with a good received signal level in order to achieve low error rates.
Virtually all known GPS receivers utilize correlation methods, or their mathematical equivalents, to compute pseudoranges. These correlation methods are performed in real time, often with hardware correlators. GPS signals contain high rate repetitive signals that are modulated in accordance with special sequences or “codes”, called pseudorandom (PN) sequences. The codes available for civilian applications are called C/A codes, and are utilized to provide a binary phase-reversal rate, or “chipping” rate, of 1.023 MHz and a repetition period of 1023 chips for a code period of 1 msec. The pseudorandom sequences in the GPS system belong to a family known as “Gold codes”. Each GPS satellite broadcasts a signal with a unique Gold code.
For brevity, in the following discussion, we may use the terminology that a signal “contains a pseudorandom sequence” (or code), by which we mean it contains a waveform that is modulated in accordance with a pseudorandom sequence, or code The length of a frame of a pseudorandom sequence is the number of symbols of the sequence before it repeats. By the duration (in time) of a pseudorandom sequence we mean the duration of the waveform modulated in accordance with the pseudorandom sequence. Similarly, when we say frame rate of a pseudorandom sequence we mean the repetition rate of a waveform modulated in accordance with the pseudorandom sequence. It should be clear from the context whether the term pseudorandom sequence refers to a sequence of numbers or a waveform modulated according to such a sequence of numbers.
For a signal received from a given GPS satellite, following a down-conversion process to baseband, the signal is then correlated with a reference signal. For example, a simple correlation receiver multiplies the received signal by a locally generated reference signal containing a stored replica of the appropriate Gold code contained within its local memory, and then integrates, (e.g. lowpass filters) the product in order to obtain an indication of the presence of the signal. This process is termed a coherent processing operation. Often the results of multiple successive coherent processing operations are detected (e.g., their magnitudes are determined) and combined in order to provide a final correlation output with higher fidelity. Hence, the initial correlation operations are coherent processing ones, and the latter combining step is called “noncoherent” or “incoherent” processing. In summary, correlation may include only coherent processing, or it may also include incoherent processing of the correlation output of two or more coherent processing steps. The final output of a succession of such correlation processing steps is termed a “final correlation output”.
In this discussion a simple individual correlation process results in a single number (perhaps complex). However, in many cases of interest a multiplicity of such numbers are computed corresponding to different reference sequences (e.g. delayed versions), either serially or in parallel, by performing similar operations. We refer to such a set of numbers as a “correlation series”. The final result of combining one or more successive correlation series is referred to as a “final correlation series.”
By sequentially adjusting the relative timing of this stored replica relative to the received signal, and observing when high energy occurs in the resulting final correlation series, a simple receiver can determine the time delay between the received signal and a local clock. This time delay, modulo the 1 millisecond code period, is termed the “code phase.” The initial determination of the presence of such an output is termed “acquisition.” Once acquisition occurs, the process enters the “tracking” phase in which the timing of the local reference is adjusted in small amounts in order to maintain a high correlation output. The correlation output during the tracking phase may be viewed as the GPS signal energy with the pseudorandom code removed, or, in common terminology, “despread.” This signal is narrow band, with bandwidth commensurate with a 50 bit per second (bps) binary-phase-shift-keyed data signal that is superimposed on the GPS waveform.
Unfortunately, the correlation acquisition process is very time consuming, especially if received signals are weak. To improve acquisition time, most conventional GPS receivers utilize a multiplicity of correlators (up to 12 typically) which allows a parallel search for correlation peaks.
Some prior GPS receivers have used FFT techniques to determine the Doppler frequency of the received GPS signal. These receivers utilize conventional correlation operations to despread the GPS signal and provide a narrow band signal with bandwidth typically in the range of 10 kHz to 30 kHz. The resulting narrow band signal is then Fourier analyzed using FFT algorithms to determine the carrier frequency. The determination of such a carrier simultaneously provides an indication that the local PN reference is adjusted to the correct code phase of the received signal and provides an accurate measurement of carrier frequency. This frequency may then be utilized in the tracking operation of the receivers.
As mentioned above, the increasing popularity of personal position location devices has encouraged development of rapid, high sensitivity methods for acquiring the GPS signals used to determine position. One method, for example, uses an FFT algorithm to compute pseudoranges at a central processing location rather than at a mobile unit. According to that method, a snapshot of data is collected by a GPS receiver and then transmitted over a data link to a remote receiver where it undergoes FFT processing in order to compute the final correlation series. However, typically, only a single forward and inverse Fast Fourier Transform (corresponding to four PN periods) are computed to perform the set of correlations.
Another approach uses fast Fourier transform methods for acquiring GPS signals includes digitizing, storing, and processing a long block of raw data. For example, data corresponding to a one-second interval can be digitized and then processed locally using an FFT-based signal processing method to acquire the GPS signals present within this captured data block. In this method a multiplicity of FFT operations are performed, each producing a correlation series, and the results undergo both coherent and incoherent processing operations in order to produce the final correlation series.
Unfortunately, the GPS signal acquisition approach in such systems becomes less efficient when performing very long coherent integrations, such as those exceeding a period of one data bit (e.g., 20 GPS frames, which equals 20 milliseconds of time); the efficiency loss is especially great when the GPS carrier frequency uncertainty is large. Furthermore, it may be noted that in current GPS receiving systems coherent integration over periods exceeding one data bit requires that the GPS receiver have a priori knowledge of the bit sequence. Therefore, coherent integration over periods exceeding one data bit is normally done by transmitting such information from a server to a mobile station. This general approach has been standardized in several cellular communications standards, including IS-95, CDMA-2000, GSM, and UMTS standards. It should be noted that future GPS systems may have modes or signaling components that transmit PN signals containing no data. Hence in the future, there may be situations in which long coherent integration may be accomplished without the need for the receiver to have a priori knowledge of such a bit sequence.
Other prior approaches to coherent processing may be useful when (1) long coherent integration is required, (2) a search over a wide Doppler range is required, and (3) a code phase search must be performed over the full 1023 chips of each GPS signal to be processed. Such prior approaches, however, have a number of limitations and restrictions. For example, these algorithms may require processing data as a two-dimensional array and also limit the extent over which a Doppler search may be efficiently performed.